package com.kobe.algorithm.leetcode.case15;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author ：caopengfei
 * @date ：2021/2/24
 * P0+P2 = -P1
 *
 */
public class Solution {


    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
      int n = nums.length;
      //数组排序
      Arrays.sort(nums);
      // 开始枚举A
        for (int first = 0; first < n; first++) {
            if(first > 0 && nums[first]  == nums[first-1]){
                continue;
            }
            int target = -(nums[first]);
            int thrid = n-1;
            //开始枚举B
            for (int second = first+1; second < n; second++) {
                 // 数字去重
                if(second > first+1 &&  nums[second]  == nums[second-1]){
                    continue;
                }

                //开始启动thrid指针
                while(second < thrid && nums[second]+nums[thrid] > target){
                     --thrid;
                }
                if(thrid == second){
                    break;
                }

                if (nums[second]+nums[thrid] == target){
                    List<Integer> group = new ArrayList<>();
                    group.add(nums[first]);
                    group.add(nums[second]);
                    group.add(nums[thrid]);
                    result.add(group);
                }
            }
        }
        return  result;

    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int [] nums = {-1,0,1,2,-1,-4};
        System.out.println(solution.threeSum(nums));

    }


}
